Media retargeting has become an important problem due to the diversity of display devices and versatility of media sources for both images and video (i.e. media). In the context of the present patent application and in the claims, “retargeting” means changing the size or aspect ratio of an image or video without distorting key areas of interest. In this process, a retargeting operator (e.g., scaling or cropping) is applied to input media, thereby adapting the media to accommodate different display devices, varying across resolution and aspect ratios. The resulting target media size may be smaller or larger than the original. Simple methods that apply uniform scaling in one direction to the media can cause main objects to shrink or expand, and give a scene an unnatural appearance. Another common method is padding the content using margins (letterbox) while maintaining the media's original aspect ratio. Such methods do not really change the original size, and do not utilize the entire display space. Simple non-uniform scaling techniques apply some inverse Gaussian scaling kernel over the media, such that the borders are scaled more extensively than the middle, under the assumption that main objects tend to appear in the center of frames. However, this assumption is not always valid, and these simple techniques can cause distortions to the media.
Recently, a content-aware retargeting method (i.e. operator) was introduced, called seam carving, as described in U.S. Patent Application Publications US 2008/0219587 and 2008/0267528, whose disclosures are incorporated herein by reference. Seam carving operates on “seams”, i.e. sequences of vertically, horizontally, or diagonally adjacent pixels that run from one side of the image to the other, one per column (for horizontal seams) or one per row (for vertical seams). Pixel importance is generally estimated by its contrast when compared with its neighbor pixels, but other measures may be used. Seam carving identifies seams comprising pixels of “less importance”. Removing all pixels in a seam reduces the height or width of the image by one row or column. Repeated removal of seams can achieve any amount of shrinking. Conversely, seam carving can be adapted to image enlargement by duplicating the pixels in a seam.